Compressed Sensing of Block-Sparse Signals: Uncertainty Relations and Efficient Recovery

摘要

We consider compressed sensing of block-sparse signals, i.e., sparse signalsthat have nonzero coefficients occurring in clusters. An uncertainty relationfor block-sparse signals is derived, based on a block-coherence measure, whichwe introduce. We then show that a block-version of the orthogonal matchingpursuit algorithm recovers block $k$-sparse signals in no more than $k$ stepsif the block-coherence is sufficiently small. The same condition onblock-coherence is shown to guarantee successful recovery through a mixed$\ell_2/\ell_1$-optimization approach. This complements previous recoveryresults for the block-sparse case which relied on small block-restrictedisometry constants. The significance of the results presented in this paperlies in the fact that making explicit use of block-sparsity can provably yieldbetter reconstruction properties than treating the signal as being sparse inthe conventional sense, thereby ignoring the additional structure in theproblem.